#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
  int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
    int length = gas.size();
    int curGas = 0;

    int i;
    int j;

    // vector<int> rest(length, 0);
    // rest[ri] = rest[ri-1] -cost[ri-1] + gas[ri];
    if (length == 1) {
      return gas[0] - cost[0] >= 0 ? 0 : -1;
    }

    int minGas = 10000;
    int minIdx = 0;
    curGas = gas[0];
    bool canReach = true;
    for (int ri = 1; ri < length; ri++) {
      int lastIdx = (ri - 1) % length;
      int curIdx = ri % length;
      int diff = curGas - cost[lastIdx];
      if (diff < 0 && diff < minGas) {
        minGas = diff;
        minIdx = ri;
        canReach = false;
        // printf("diff:%d, minGas:%d, lastIdx:%d\n", diff,minGas, lastIdx);
      }
      curGas += gas[curIdx] - cost[lastIdx];
    }

    if (canReach) {
      return 0;
    }

    // printf("get minIdx:%d\n", minIdx);

    curGas = gas[minIdx];
    for (int ri = 1; ri <= length; ri++) {
      int lastIdx = (minIdx + ri - 1) % length;
      int curIdx = (minIdx + ri) % length;

      if (curGas < cost[lastIdx]) {
        return -1;
      }
      curGas += gas[curIdx] - cost[lastIdx];
    }

    return minIdx;
  }
};

void testcase01() {
  printf("test case 01\n");
  vector<int> gas;
  vector<int> cost;

  gas.push_back(1);
  gas.push_back(2);
  gas.push_back(3);
  gas.push_back(4);
  gas.push_back(5);

  cost.push_back(3);
  cost.push_back(4);
  cost.push_back(5);
  cost.push_back(1);
  cost.push_back(2);

  Solution so;
  int expect = 3;
  int got = so.canCompleteCircuit(gas, cost);
  if (got != expect) {
    printf("err! expect:%d, but got: %d\n", expect, got);
  } else {
    printf("success! got: %d\n", got);
  }
}

void testcase02() {
  printf("test case 02\n");
  vector<int> gas;
  vector<int> cost;

  gas.push_back(2);
  gas.push_back(3);
  gas.push_back(4);

  cost.push_back(3);
  cost.push_back(4);
  cost.push_back(3);

  Solution so;
  int expect = -1;
  int got = so.canCompleteCircuit(gas, cost);
  if (got != expect) {
    printf("err! expect:%d, but got: %d\n", expect, got);
  } else {
    printf("success! got: %d\n", got);
  }
}

void testcase03() {
  printf("test case 03\n");
  vector<int> gas;
  vector<int> cost;

  gas.push_back(3);
  gas.push_back(1);
  gas.push_back(1);

  cost.push_back(1);
  cost.push_back(2);
  cost.push_back(2);

  Solution so;
  int expect = 0;
  int got = so.canCompleteCircuit(gas, cost);
  if (got != expect) {
    printf("err! expect:%d, but got: %d\n", expect, got);
  } else {
    printf("success! got: %d\n", got);
  }
}

void testcase04() {
  printf("test case 04\n");
  vector<int> gas;
  vector<int> cost;

  gas.push_back(4);

  cost.push_back(5);

  Solution so;
  int expect = -1;
  int got = so.canCompleteCircuit(gas, cost);
  if (got != expect) {
    printf("err! expect:%d, but got: %d\n", expect, got);
  } else {
    printf("success! got: %d\n", got);
  }
}

int main() {
  testcase01();
  testcase02();
  testcase03();
  testcase04();
  return 0;
}
